import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/6/30
 * \* Time: 20:21
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 打开转盘锁 {
    public int openLock(String[] deadends, String target) {
        //记录需要跳过的死亡密码
        Set<String> deads=new HashSet<>();
        for(String deadend:deadends){
            deads.add(deadend);
        }

        Set<String> visited = new HashSet<>();
        Queue<String> q=new LinkedList<>();
        //从起点开始进行BFS
        int step=0;
        q.offer("0000");
        visited.add("0000");
        while (!q.isEmpty()){
            int sz=q.size();
            for(int i=0;i<sz;i++){
                String cur=q.poll();
                //判断密码是否合法，即是否到达终点
                if(cur.equals(target)){
                    return step;
                }
                //如果是死亡密码或者之前已经到过这一步直接跳过这个数字的后续情况
                if(deads.contains(cur)){
                    continue;
                }

                //将当前密码的4个位置的向上拨动和向下拨动情况加入队列
                for(int j=0;j<4;j++){
                    String up=plusOne(cur,j);
                    //如果是个新密码切不包含在之前的密码里面则加入队列
                    if(!visited.contains(up)){
                        q.offer(up);
                        visited.add(up);
                    }

                    String down=minusOne(cur,j);
                    if(!visited.contains(down)){
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            //弄完一轮则步数➕1
            step++;
        }
        //枚举完了都没找到目标数字则返回-1
        return -1;
    }

    /**
     * 把s[j]向上拨动一次
     * @param s
     * @param j
     * @return
     */
    String plusOne(String s,int j){
        char[] ch=s.toCharArray();
        if(ch[j]=='9'){
            ch[j]='0';
        }else{
            ch[j]+=1;
        }
        return new String(ch);
    }

    String minusOne(String s,int j){
        char[] ch=s.toCharArray();
        if(ch[j]=='0'){
            ch[j]='9';
        }else{
            ch[j]-=1;
        }
        return new String(ch);
    }

}